/*
 * Copyright (C) 2008,2009,2010,2011  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

/*
 * Prototypes
 */
static eint32_t
empz_hash(empz_t z);

static eint32_t
empq_hash(empq_t q);

static eint32_t
empr_hash(empr_t r);

static eint32_t
ecqq_hash(ecqq_t qq);

static eint32_t
empc_hash(empc_t rr);

static eint32_t
object_hash(ehash_t *hash, eobject_t name);

static inline ebool_t
empr_cmp(empr_t a, empr_t b);

static ebool_t
object_cmp(ehash_t *hash,
	   eobject_t left, eobject_t right, etype_t type, eint32_t lenght);

static eint32_t
find_prime(eint32_t size);

static void
rehash(ehash_t *hash, ebool_t resize);

/*
 * Initialization
 */
static eint32_t primes[] = {
       5,   11,   17,   23,
      31,   47,   71,   97,
     139,  199,  307,  401,
     607,  809, 1213, 1619,
    2437, 3251, 4889, 6521
};

ehash_t	*ht_root;
ehash_t	*ht_current;
ehash_t	*ht_language;

/*
 * Implementation
 */
void
init_hash(void)
{
    enew_hash((eobject_t *)&ht_language, H_string, 11);
    eadd_root((eobject_t *)&ht_language);
    enew_hash((eobject_t *)&ht_root, H_string, 139);
    eadd_root((eobject_t *)&ht_root);
    ht_current = ht_root;
}

void
enew_hash(eobject_t *pointer, eint32_t mode, eint32_t size)
{
    ehash_t	*hash;
    v_enter();

    enew_object(pointer, t_hash, sizeof(ehash_t));
    hash = *(ehash_t **)pointer;
    hash->count = 0;

    size = find_prime(size);
    v_check(1);
    v_push(hash);
    enew_object((eobject_t *)&hash->entries, t_resize | t_void,
		size * sizeof(eentry_t *));
    /* Set hash size after allocating entries or gc can dereference it */
    hash->size = size;
    hash->memory = mode != 0;
    v_leave();
}

eint32_t
estr_hash(euint8_t *name, eint32_t length)
{
    euint8_t	*ptr;
    eint32_t	 i, key;

    for (i = key = 0, ptr = name; i < length; i++)
	key = (key << (key & 1)) ^ ptr[i];

    return (key & 0x7fffffff);
}

static inline eint32_t
eint_hash(eint32_t *vector, eint32_t key, eint32_t length)
{
    eint32_t	i;

    for (i = 0; i < length; i++)
	key ^= vector[i];

    return (key & 0x7fffffff);
}

static eint32_t
empz_hash(empz_t z)
{
    eint32_t	key;
    eint32_t	length;

    if (z->_mp_size < 0) {
	key = -1;
	length = -z->_mp_size;
    }
    else {
	key = 0;
	length = z->_mp_size;
    }

#if __WORDSIZE == 64
    length <<= 1;
#endif

    return (eint_hash((eint32_t *)z->_mp_d, key, length));
}

static eint32_t
empq_hash(empq_t q)
{
    return (empz_hash(mpq_numref(q)) ^ empz_hash(mpq_denref(q)));
}

static eint32_t
empr_hash(empr_t r)
{
    eint32_t	key;
    eint32_t	length;

    /* valgrind warning: don't hash uninitialized data; this mpfr_t
     * may be a pure nan/inf or never set to a number other than zero */
    if (!mpfr_number_p(r) || mpfr_zero_p(r))
	return (0);

    if (r->_mpfr_sign < 0)
	key = -1;
    else
	key = 0;

    length = (r->_mpfr_prec - 1) / GMP_LIMB_BITS;
#if __WORDSIZE == 64
    length <<= 1;
#endif
    key = eint_hash((eint32_t *)r->_mpfr_d, key, length);

    return ((key ^ r->_mpfr_exp) & 0x7fffffff);
}

static eint32_t
ecqq_hash(ecqq_t qq)
{
    return (empq_hash(cqq_realref(qq)) ^ empq_hash(cqq_imagref(qq)));
}

static eint32_t
empc_hash(empc_t rr)
{
    return (empr_hash(mpc_realref(rr)) ^ empr_hash(mpc_imagref(rr)));
}

static eint32_t
object_hash(ehash_t *hash, eobject_t name)
{
    if (!hash->memory && name != null && !efixnum_p(name)) {
	switch (eobject_type(name)) {
	    case t_mpz:	return (empz_hash(name));
	    case t_mpq:	return (empq_hash(name));
	    case t_mpr: return (empr_hash(name));
	    case t_cqq: return (ecqq_hash(name));
	    case t_mpc: return (empc_hash(name));
	    default:	return (estr_hash(name, eobject_length(name)));
	}
    }
    return (estr_hash((euint8_t *)&name, sizeof(eobject_t)));
}

static inline ebool_t
empr_cmp(empr_t a, empr_t b)
{
    if (mpfr_signbit(a) == mpfr_signbit(b)) {
	if (likely(mpfr_number_p(a))) {
	    if (likely(mpfr_number_p(b)))
		return (mpfr_lessgreater_p(a, b) == 0);
	    return (false);
	}
	if (likely(!mpfr_number_p(b))) {
	    if (mpfr_nan_p(a))
		return (mpfr_nan_p(b));
	    return (mpfr_inf_p(b));
	}
    }
    return (false);	
}

static ebool_t
object_cmp(ehash_t *hash,
	   eobject_t left, eobject_t right, etype_t type, eint32_t length)
{
    etype_t	rtype;

    if (left == right)				return (true);
    if (hash->memory)				return (false);
    if ((type & t_fixnum) || efixnum_p(right))	return (false);
    if (left == null || right == null)		return (false);
    rtype = eobject_type(right) & ~t_const;
    if (rtype != type)				return (false);
    switch (type) {
	case t_mpz:
	    return (mpz_cmp(left, right) == 0);
	case t_mpq:
	    return (mpq_cmp(left, right) == 0);
	case t_mpr:
	    return (empr_cmp(left, right));
	case t_cqq:
	    return (mpq_cmp(cqq_realref((ecqq_t)left),
			    cqq_realref((ecqq_t)right)) == 0 &&
		    mpq_cmp(cqq_imagref((ecqq_t)left),
			    cqq_imagref((ecqq_t)right)) == 0);
	case t_mpc:
	    return (empr_cmp(mpc_realref((empc_t)left),
			     mpc_realref((empc_t)right)) &&
		    empr_cmp(mpc_imagref((empc_t)left),
			     mpc_imagref((empc_t)right)));
	default:
	    return (length == eobject_length(right) &&
		    memcmp(left, right, length) == 0);
    }
}

eentry_t *
eput_hash(ehash_t *hash, eentry_t *entry)
{
    eint32_t	 key;
    etype_t	 type;
    eint32_t	 length;
    eentry_t	*prev, *ptr;

    /* Offset in hash table vector for this entry */
    entry->key = object_hash(hash, entry->name);
    key = entry->key % hash->size;

    /* We hope this is null for most calls */
    ptr = hash->entries[key];

    if (efixnum_p(entry->name))
	type = t_fixnum;
    else
	type = eobject_type(entry->name) & ~t_const;
    length = eobject_length(entry->name);
    /* Check if clashed with another entry */
    for (prev = ptr; ptr; prev = ptr, ptr = ptr->next) {
	/* Replace current entry */
	if (object_cmp(hash, entry->name, ptr->name, type, length)) {
	    /* If not trying to readd same value */
	    if (entry != ptr) {
		if (ptr == prev)
		    hash->entries[key] = entry;
		else
		    prev->next = entry;
		entry->next = ptr->next;
		/* Finished */
	    }
	    else
		ptr = null;
	    goto eput_hash_done;
	}
    }

    /* Add new entry */
    if (prev == null)
	/* If no entry in offset */
	hash->entries[key] = entry;
    else
	/* Add to end of clashing list */
	prev->next = entry;
    /* Should already be null, but for safety */
    entry->next = null;

    /* Increase sum of entries counter */
    ++hash->count;

    /* Check if should rehash */
    if (hash->count > hash->size * 0.75)
	rehash(hash, true);

eput_hash_done:
    /* ptr will be null if no entry was replaced, of tried to add
     * again an entry already in the hash table */
    return (ptr);
}

eentry_t *
eget_hash(ehash_t *hash, eobject_t name)
{
    eint32_t	 key;
    etype_t	 type;
    eint32_t	 length;
    eentry_t	*entry;

    if (efixnum_p(name))
	type = t_fixnum;
    else
	type = eobject_type(name) & ~t_const;
    length = eobject_length(name);
    key = object_hash(hash, name) % hash->size;
    for (entry = hash->entries[key]; entry; entry = entry->next) {
	if (object_cmp(hash, name, entry->name, type, length))
	    return (entry);
    }

    return (null);
}

eentry_t *
eget_hash_entry(ehash_t *hash, eentry_t *entry)
{
    eint32_t	 key;
    eobject_t	 name;
    etype_t	 type;
    eint32_t	 length;

    name = entry->name;
    key = entry->key % hash->size;
    if (efixnum_p(name))
	type = t_fixnum;
    else
	type = eobject_type(name) & ~t_const;
    length = eobject_length(name);
    for (entry = hash->entries[key]; entry; entry = entry->next) {
	if (object_cmp(hash, name, entry->name, type, length))
	    return (entry);
    }

    return (null);
}

eentry_t *
eget_hash_string(ehash_t *hash, euint8_t *name, eint32_t length)
{
    eint32_t	 key;
    eentry_t	*entry;

    key = estr_hash(name, length) % hash->size;
    for (entry = hash->entries[key]; entry; entry = entry->next) {
	if (object_cmp(hash, name, entry->name, t_resize | t_uint8, length))
	    return (entry);
    }

    return (null);
}

eentry_t *
erem_hash(ehash_t *hash, eentry_t *entry)
{
    eint32_t	 key;
    eentry_t	*ptr, *prev;

    key = entry->key % hash->size;
    for (ptr = prev = hash->entries[key]; ptr; prev = ptr, ptr = ptr->next) {
	if (ptr == entry) {
	    --hash->count;
	    if (ptr == prev)
		hash->entries[key] = ptr->next;
	    else
		prev->next = ptr->next;
	    break;
	}
    }

    /* If entry wasn't in hash table ptr will be null */
    return (ptr);
}

void
eclr_hash(ehash_t *hash)
{
    if (hash->count) {
	hash->count = 0;
	/* let gc collect it */
	memset(hash->entries, 0, sizeof(eobject_t) * hash->size);
    }
}

static eint32_t
find_prime(eint32_t size)
{
    eint32_t	i;

    for (i = 0; i < esize(primes); i++)
	if (primes[i] >= size)
	    return (primes[i]);

    return (size);
}

void
erehash(ehash_t *hash)
{
    rehash(hash, false);
}

static void
rehash(ehash_t *hash, ebool_t resize)
{
    eint32_t	 i, size, key;
    eentry_t	*entry, *next, **entries;
    v_enter();

    if (resize) {
	size = find_prime(hash->size + 1);
	if (size == hash->size + 1)
	    size = (hash->size * 2) & 0x7fffffff;
    }
    else
	size = hash->size;
    v_check(1);
    v_push(hash);
    enew_object((eobject_t *)&entries, t_resize | t_void,
		size * sizeof(eentry_t *));

    /* Populate the new table, note that clashes are now in reverse order */
    for (i = 0; i < hash->size; i++) {
	for (entry = hash->entries[i]; entry; entry = next) {
	    next = entry->next;
	    key = entry->key % size;
	    entry->next = entries[key];
	    entries[key] = entry;
	}
    }

    /* Finish updating hash table */
    hash->entries = entries;
    hash->size = size;
    v_leave();
}
